﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace SortGUI
{
    public class QuickSort : SortBase
    {
        override public void Sort(int[] alNum)
        {
            Initialize();
            QuickSortRecursive(alNum, 0, alNum.Length - 1);
            Complete();
        }

        private void QuickSortRecursive(int[] alNum, int low, int high)
        {
            if (low < high)
            {
                int pivotIndex = Partition(alNum, low, high);
                QuickSortRecursive(alNum, low, pivotIndex - 1);
                QuickSortRecursive(alNum, pivotIndex + 1, high);
            }
        }

        private int Partition(int[] alNum, int low, int high)
        {
            int pivot = alNum[high];
            int i = low - 1;

            for (int j = low; j < high; j++)
            {
                if (alNum[j] <= pivot)
                {
                    i++;
                    Swap(ref alNum[i], ref alNum[j]);
                    lastSwappedIndices[0] = i;
                    lastSwappedIndices[1] = j;
                    swapped = true;
                    count++;
                    SortNextStep();
                }
            }
            Swap(ref alNum[i + 1], ref alNum[high]);
            lastSwappedIndices[0] = i + 1;
            lastSwappedIndices[1] = high;
            swapped = true;
            count++;
            SortNextStep();
            return i + 1;
        }

        public override void Initialize()
        {
            count = 0;
            updataColor(isInitialize = false);
        }

        public override void SortNextStep()
        {
            updateUiCallback(count, lastSwappedIndices, lastSortedIndex = 10000, swapped); // 更新UI
        }

        public override void Complete()
        {
            updateUiCallback(count, lastSwappedIndices, lastSortedIndex - 10000, swapped);
        }
    }
}
